package 第三周;

/*
 * @author  YxinMiracle
 * @date  2022-04-26 19:52
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.ArrayList;
import java.util.List;

public class 全排列 {
    // 公共遍历记得回归现场
    public boolean[] used;
    public int n; // 记录有几个数字
    public List<List<Integer>> result = new ArrayList<>();
    public List<Integer> temp = new ArrayList<>();


    public List<List<Integer>> permute(int[] nums) {
        n = nums.length;
        used = new boolean[n];
        for (int i = 0; i < n; i++) {
            used[i] = false;
        }
        recur(nums,0);
        return result;
    }

    // 递归
    public void recur(int[] nums,int length){
        if (length == n){
            // 记录答案
            List<Integer> list = new ArrayList<>(temp);
            result.add(list);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!used[i]){
                // 如果这个数没有被使用过
                temp.add(nums[i]);
                used[i] = true; // 标记为使用过
                recur(nums,length+1);
                // 还原现场
                used[i] = false;
                temp.remove(temp.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new 全排列().permute(new int[]{1,2,3}));
    }



}
